import java.util.ArrayList;
import java.util.List;

class Solution {
    public int numDecodings(String ss) {
        int n=ss.length();
        int[] dp=new int[n];
        char[] s=ss.toCharArray();

        if(s[0]=='0'){
            return 0;
        }

        dp[0]=1;
        if(n==1){
            return 1;
        }

        if(s[1]!='0'){
            dp[1]++;
        }
        int tt=(s[0]-'0')*10+s[1]-'0';
        if(tt>=10 && tt<=26){
            dp[1]++;
        }

        for(int i=2;i<n;i++){
            if(s[i]!='0'){
                dp[i]+=dp[i-1];
            }
            int t=(s[i-1]-'0')*10+s[i]-'0';
            if(t>=10 && t<=26){
                dp[i]+=dp[i-2];
            }
        }
        return dp[n-1];
    }
}